package Leetcode.动态规划;

/**
 * @Author: kirito
 * @Date: 2024/3/29 13:04
 * @Description:
 * 你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。
 *
 * 最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：
 *
 * 假设某一天，你访问 i 号房间。
 * 如果算上本次访问，访问 i 号房间的次数为 奇数 ，那么 第二天 需要访问 nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
 * 如果算上本次访问，访问 i 号房间的次数为 偶数 ，那么 第二天 需要访问 (i + 1) mod n 号房间。
 * 请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 109 + 7 取余后的结果。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nextVisit = [0,0]
 * 输出：2
 * 解释：
 * - 第 0 天，你访问房间 0 。访问 0 号房间的总次数为 1 ，次数为奇数。
 *   下一天你需要访问房间的编号是 nextVisit[0] = 0
 * - 第 1 天，你访问房间 0 。访问 0 号房间的总次数为 2 ，次数为偶数。
 *   下一天你需要访问房间的编号是 (0 + 1) mod 2 = 1
 * - 第 2 天，你访问房间 1 。这是你第一次完成访问所有房间的那天。
 * 示例 2：
 *
 * 输入：nextVisit = [0,0,2]
 * 输出：6
 * 解释：
 * 你每天访问房间的次序是 [0,0,1,0,0,1,2,...] 。
 * 第 6 天是你访问完所有房间的第一天。
 * 示例 3：
 *
 * 输入：nextVisit = [0,1,2,0]
 * 输出：6
 * 解释：
 * 你每天访问房间的次序是 [0,0,1,1,2,2,3,...] 。
 * 第 6 天是你访问完所有房间的第一天。
 *x
 *
 * 提示：
 *
 * n == nextVisit.length
 * 2 <= n <= 105
 * 0 <= nextVisit[i] <= i
 *
 *
 * 根据题意，首次访问房间“时，因为我们是第一次访问，1是奇数，所以下一天一定要访问j=netVisit[i]房间，下文简称为「回访」。
 * 由于访问偶数次才能访问右边的下一个房间，所以对于，左边的房间，我们一定都访问了偶数次(不然不可能到达i)。
 * 这意味着，当我们从“回到;时，此时“,i- 1]范围内的房间都处于访问偶数次的状态。那么当我们访问这个范围内的每个房间时，
 * 算上本次访问，访问次数一定是奇数，所以要想重新回到i，对于 [,i-1] 范围内的每个房间，我们都需要执行一次「回访」。
 *
 * 对于房间i  其访问次数的奇偶性变化如下
 * 描述               奇偶性
 * 访问房间i之前          偶数     1
 *
 * 访问到房间i            奇数     2
 *
 * 回访完毕，
 * 重新回到房间i          偶数      3
 *
 *
 * 说明2-3-1是一个周期
 */


public class firstDayBeenInAllRooms {
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        int mod = 1000000007; // 定义模数，用于防止整数溢出，常见于编程竞赛中的题目
        int len = nextVisit.length; // 获取nextVisit数组的长度
        int[] dp = new int[len]; // 创建一个动态规划数组dp

        // 初始化dp数组的第一个元素，代表到达第一个房间需要的天数
        // 可以选择原地待一天或者去访问下一个房间一天
        dp[0] = 2;

        for (int i = 1; i < len; i++) { // 遍历数组，从第二个元素开始
            int to = nextVisit[i]; // 获取到下一个房间的索引
            dp[i] = 2 + dp[i - 1]; // 到达当前房间所需的天数等于前一天加上2
            if (to != 0) { // 如果存在下一个房间
                dp[i] = (dp[i] - dp[to - 1] + mod) % mod; // 更新当前房间的天数
                // 避免出现负数，并且使用模运算保持结果在整数范围内
            }

            dp[i] = (dp[i] + dp[i - 1]) % mod; // 当前房间的天数加上前一天的天数对模数取余
        }
        return dp[len - 2]; // 返回到达最后一个房间之前的天数，题目保证至少有两个房间
    }

}
